package com.lw.leetcode.tree.b;


import com.lw.leetcode.linked.ListNode;

/**143. 重排链表
 * 剑指 Offer II 026. 重排链表
 * @Author liw
 * @Date 2021/4/29 15:43
 * @Version 1.0
 */
public class ReorderList {

    public static void main(String[] args) {
        ReorderList test = new ReorderList();
        ListNode instance = ListNode.getInstance();
        test.reorderList(instance);
        System.out.println(instance);

    }

    public void reorderList(ListNode head) {
        if (head == null || head.next == null || head.next.next == null) {
            return;
        }
        // 寻找中点
        ListNode a = head;
        ListNode b = head;

        while (b != null && b.next != null) {
            a = a.next;
            b = b.next.next;
        }
        b = reverse(a);
        a = head;
        ListNode node = new ListNode(0);
        while (a != null && b != null) {
            if (a == b) {
                node.next = a;
                break;
            } else {
                node.next = a;
                a = a.next;
                node.next.next = b;
                b = b.next;
                node = node.next.next;
            }
        }
    }

    // 反转
    private static ListNode reverse (ListNode head) {

        if (head == null || head.next == null) {
            return head;
        }
        ListNode reverse = reverse(head.next);
        head.next.next = head;
        head.next = null;
        return reverse;
    }

}
